Search for: All records

We show that if ${\mathcal{L}}_1$and ${\mathcal{L}}_2$are linear transformations from ${\mathbb{Z}}^d$to ${\mathbb{Z}}^d$satisfying certain mild conditions, then, for any finite subset $A$of ${\mathbb{Z}}^d$, $|{\mathcal{L}}_{1}A+{\mathcal{L}}_{2}A|\ge <\#comment/>{(|det({\mathcal{L}}_1){|}^{1/d}+|det({\mathcal{L}}_2\left){|}^{1/d}\right)}^d|A|-<\#comment/>o\left(|A|\right).$This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for certain choices of ${\mathcal{L}}_1$and ${\mathcal{L}}_2$. As an application, we prove a lower bound for $|A+\mathrm{\lambda <\#comment/>}\cdot <\#comment/>A|$when $A$is a finite set of real numbers and $\mathrm{\lambda <\#comment/>}$is an algebraic number. In particular, when $\mathrm{\lambda <\#comment/>}$is of the form $(p/q{)}^{1/d}$for some $p,q,d\in <\#comment/>\mathbb{N}$, each taken as small as possible for such a representation, we show that $|A+\mathrm{\lambda <\#comment/>}\cdot <\#comment/>A|\ge <\#comment/>(p^{1/d}+q^{1/d}{)}^d|A|-<\#comment/>o(|A|).$This is again best possible up to the lower-order term and extends a recent result of Krachun and Petrov which treated the case $\mathrm{\lambda <\#comment/>}=\sqrt{2}$. 

Abstract A fundamental problem in Ramsey theory is to determine the growth rate in terms of $$n$$ of the Ramsey number $$r(H, K_{n}^{(3)})$$ of a fixed $$3$$-uniform hypergraph $$H$$ versus the complete $$3$$-uniform hypergraph with $$n$$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $$H$$, including links of odd cycles and tight cycles of length not divisible by three, $$r(H, K_{n}^{(3)}) \ge 2^{\Omega _{H}(n \log n)}$$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $$H$$ for which $$r(H, K_{n}^{(3)})$$ is superpolynomial in $$n$$. This provides the first example of a separation between $$r(H,K_{n}^{(3)})$$ and $$r(H,K_{n,n,n}^{(3)})$$, since the latter is known to be polynomial in $$n$$ when $$H$$ is linear. 

Abstract We showthat for every integer $$k\geqslant 3$$ the set of Turán densities of $$k$$-uniform hypergraphs has an accumulation point in $[0,1)$. In particular, $1/2$ is an accumulation point for the set of Turán densities of $$3$$-uniform hypergraphs. 

Abstract We say that a graphHdominates another graphH^′if the number of homomorphisms fromH^′to any graphGis dominated, in an appropriate sense, by the number of homomorphisms fromHtoG. We study the family of dominating graphs, those graphs with the property that they dominate all of their subgraphs. It has long been known that even-length paths are dominating in this sense and a result of Hatami implies that all weakly norming graphs are dominating. In a previous paper, we showed that every finite reflection group gives rise to a family of weakly norming, and hence dominating, graphs. Here we revisit this connection to show that there is a much broader class of dominating graphs. 

Abstract Sidorenko’s conjecture states that, for all bipartite graphs $$H$$, quasirandom graphs contain asymptotically the minimum number of copies of $$H$$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko’s conjecture does not hold for a particular $$r$$-partite $$r$$-uniform hypergraph $$H$$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $$\textrm{ex}(n,H)$$, the maximum number of edges in an $$n$$-vertex $$H$$-free $$r$$-uniform hypergraph. With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $$3$$-partite $$3$$-uniform tight cycles. 

For positive integers 𝑛, 𝑟, 𝑠 with 𝑟 > 𝑠, the set-coloring Ramsey number 𝑅(𝑛; 𝑟, 𝑠) is the minimum 𝑁 such that if every edge of the complete graph 𝐾_𝑁 receives a set of 𝑠 colors from a palette of 𝑟 colors, then there is guaranteed to be a monochromatic clique on 𝑛 vertices, that is, a subset of 𝑛 vertices where all of the edges between them receive a common color. In particular, the case 𝑠 = 1 corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on 𝑅(𝑛; 𝑟, 𝑠) which imply that 𝑅(𝑛; 𝑟, 𝑠) = 2^Θ(𝑛𝑟) if 𝑠/𝑟 is bounded away from 0 and 1. The upper bound extends an old result of Erdős and Szemerédi, who treated the case 𝑠 = 𝑟 − 1, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.